// https://leetcode.cn/problems/3sum-closest/

// 题干：给你一个长度为 n 的整数数组 nums 和 一个目标值 target。
// 请你从 nums 中选出三个整数，使它们的和与 target 最接近。
// 假定每组输入只存在恰好一个解。


// 示例：
// 输入：nums = [-1,2,1,-4], target = 1     输出：2

// 碎语：双指针来优化，暴力O(N^3)肯定过不了

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;

#include <string>
#include <algorithm>
#include <vector>
#include <cmath>

class Solution
{
public:
    int threeSumClosest(vector<int>& nums, int target)
    {
        sort(nums.begin(), nums.end());

        pair<int, int> res(INT_MAX, INT_MAX);

        for (int i = 0; i < nums.size(); i++)
        {
            for (int j = i + 1, k = nums.size() - 1; j < k; j++)
            {
                while (j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= target) k--;

                int s = nums[i] + nums[j] + nums[k];
                res = min(res, make_pair(abs(s - target), s));

                if (j < k - 1)
                {
                    s = nums[i] + nums[j] + nums[k - 1];
                    res = min(res, make_pair(abs(s - target), s));
                }
            }
        }

        return res.second;
    }
};

int main()
{
    vector<int> nums = { -1,2,1,-4 };

    cout << Solution().threeSumClosest(nums, 1) << endl;

    return 0;
}